package 题目集.图.最短路;

import java.util.*;

/**
 * dj特斯拉算法
 * https://pintia.cn/problem-sets/1728617645410041856/exam/problems/1728617696303685645?type=7&page=0
 */
public class 垃圾箱分布 {

    /**
     * 思路：
     * 通过dj特斯拉算法，计算以每个垃圾点为根，到所有居民点的最短距离。
     * 再将每个垃圾点距离居民点的平均距离入小根堆。取堆顶元素。
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int k = sc.nextInt();
        int limit = sc.nextInt();
        sc.nextLine();
        String[] src = new String[k];
        String[] target = new String[k];
        Integer[] weight = new Integer[k];
        while (k-- > 0) {
            String[] s = sc.nextLine().split(" ");
            src[k] = s[0];
            target[k] = s[1];
            weight[k] = Integer.parseInt(s[2]);
        }
        Graph graph = new Graph(src, target, weight, n);
        fun(graph, n, m, limit);
    }

    public static int[] dijkstra(Graph graph,int n,int m,Node start){
        int[] distances = new int[n + m];
        Arrays.fill(distances,Integer.MAX_VALUE);
        NodeHeap heap=new NodeHeap(n+m);
        heap.addOrUpdateOrIgnore(start,0);
        while (heap.isNotEmpty()){
            NodeHeap.NodeRecord curr = heap.pop();
            distances[curr.node.val-1]=curr.distance;
            for (Edge edge : curr.node.edges) {
                heap.addOrUpdateOrIgnore(edge.to,curr.distance+edge.weight);
            }
        }
        return distances;
    }

    public static String fun(Graph graph, int n, int m, int limit) {
        ResNode res = null;
        for (int i = 1; i <= m; i++) {
            Node start=graph.nodes.get(n+i);
            int[] distances = dijkstra(graph, n, m, start);
            double min = Double.MAX_VALUE;
            boolean isOut = false;
            double sum = 0;
            for (int j = 0; j < n; j++) {
                if (distances[j] > limit) {
                    isOut = true;
                    break;
                }
                sum += distances[j];
                min = Math.min(min, distances[j]);
            }
            if (!isOut) {
                res = max(res, new ResNode("G" + (start.val - n), min, sum / n), n);
            }
        }
        if (res != null) {
//            System.out.println(res.name);
//            System.out.println(String.format("%.1f %.1f", res.min, res.avg));
            return res.name+"\t"+String.format("%.1f %.1f", res.min, res.avg);
        } else {
//            System.out.println("No Solution");
            return "No Solution";
        }
    }

    public static ResNode max(ResNode o1, ResNode o2, int n) {
        if (o1 == null || o2 == null) {
            return o1 == null ? o2 : o1;
        }
        if (o1.min != o2.min) {
            return o1.min > o2.min ? o1 : o2;
        }
        if (o1.avg == o2.avg) {
            return getIndex(o1.name, n) < getIndex(o2.name, n) ? o1 : o2;
        }
        return o1.avg < o2.avg ? o1 : o2;
    }

    public static int getIndex(String target, int n) {
        if (target.charAt(0) != 'G') {
            return Integer.parseInt(target);
        }
        return Integer.parseInt(target.substring(1)) + n;
    }

    static class ResNode {
        String name;
        double min;
        double avg;

        public ResNode(String name, double min, double avg) {
            this.name = name;
            this.min = min;
            this.avg = avg;
        }
    }

    static class Graph {
        public Map<Integer, Node> nodes;
        public Set<Edge> edges;

        public Graph() {
            nodes = new HashMap<>();
            edges = new HashSet<>();
        }

        public Graph(Map<Integer, Node> nodes, Set<Edge> edges) {
            this.nodes = nodes;
            this.edges = edges;
        }

        /**
         * 根据邻接矩阵数组生成图
         */
        public Graph(String[] src, String[] target, Integer[] weight, int n) {
            this();
            for (int i = 0; i < src.length; i++) {
                int srcIndex = getIndex(src[i], n);
                int targetIndex = getIndex(target[i], n);
                Node from = nodes.putIfAbsent(srcIndex, new Node(srcIndex));
                Node to = nodes.putIfAbsent(targetIndex, new Node(targetIndex));
                from = nodes.get(srcIndex);
                to = nodes.get(targetIndex);

                Edge toTo = new Edge(weight[i], from, to);
                Edge toFrom = new Edge(weight[i], to, from);

                from.nexts.add(to);
                from.edges.add(toTo);

                to.nexts.add(from);
                to.edges.add(toFrom);

                edges.add(toTo);
                edges.add(toFrom);
            }
        }
    }

    static class Node {
        Integer val;
        List<Node> nexts;    //该点的邻居
        List<Edge> edges;

        public Node(Integer val) {
            this.val = val;
            nexts = new ArrayList<>();
            edges = new ArrayList<>();
        }

        @Override
        public String toString() {
            return " " + val + " ";
        }
    }

    static class Edge {
        public Integer weight;
        public Node from;   //该边的入点
        public Node to;     //该边的出点

        public Edge(Integer weight, Node from, Node to) {
            this.weight = weight;
            this.from = from;
            this.to = to;
        }

        public Edge(Node from, Node to) {
            this.from = from;
            this.to = to;
        }
    }

    static class NodeHeap {
        Node[] nodes;
        Map<Node, Integer> indexMap;     //节点在堆中的位置
        Map<Node, Integer> distanceMap;     //节点距离起点的位置
        int heapSize;

        public NodeHeap(int size) {
            this.nodes = new Node[size];
            indexMap = new HashMap<>(size);
            distanceMap = new HashMap<>(size);
        }

        /**
         * 如果节点不存在则添加
         * 节点存在且比原来要近则更新，更远则不更新
         */
        public void addOrUpdateOrIgnore(Node node, int distance) {
            if (distanceMap.containsKey(node)) {
                if (distance < distanceMap.get(node)) {
                    heapInsert(node, indexMap.get(node), distance);
                    heapify(indexMap.get(node));
                }
                return;
            }
            heapInsert(node, heapSize++, distance);
        }

        /**
         * 返回堆中距离起点最近的节点，并将其移出至堆外
         */
        public NodeRecord pop() {
            Node node = nodes[0];
            swap(0, --heapSize); //头节点换至最后，堆的容量减一，即不要最后的节点
            heapify(0);     //在0位置上重构堆
            return new NodeRecord(node, distanceMap.get(node));
        }

        public boolean isNotEmpty() {
            return heapSize > 0;
        }

        /**
         * 插入一个节点，并为他设置距离，索引，以及入数组
         */
        public void heapInsert(Node node, int index, int distance) {
            nodes[index] = node;
            indexMap.put(node, index);
            distanceMap.put(node, distance);

            Node parentNode = nodes[(index - 1) / 2];
            while (distanceMap.get(node) < distanceMap.get(parentNode)) {    //和父亲对比，直到自己比父亲大，否则一直换下去
                swap(index, (index - 1) / 2);
                index = (index - 1) / 2;
                parentNode = nodes[index];
            }
        }

        /**
         * 从指定位置对堆进行向下重构
         */
        public void heapify(int index) {
            int left = index * 2 + 1;
            while (left < heapSize) {
                int minIndex = left + 1 < heapSize && distanceMap.get(nodes[left + 1]) < distanceMap.get(nodes[left]) ?
                        left + 1 : left;
                if (distanceMap.get(nodes[index]) < distanceMap.get(nodes[minIndex])) {   //当前节点仍是最近节点
                    return;
                }
                swap(minIndex, index);
                index = minIndex;
                left = index * 2 + 1;
            }
        }

        public void swap(int a, int b) {
            Node node = nodes[a];
            nodes[a] = nodes[b];
            nodes[b] = node;
            indexMap.put(nodes[a], a);
            indexMap.put(nodes[b], b);
        }

        static class NodeRecord {
            Node node;
            int distance;

            public NodeRecord(Node node, int distance) {
                this.node = node;
                this.distance = distance;
            }
        }
    }
}
